package program.tree;

/**
 * 线段树
 *
 * 底层实现数据结构为: 数组. 使用数组组成一棵树.
 */
public class SegmentTree<E> {

    private E[] tree;
    private E[] data;
    private Merger<E> merger;

    public SegmentTree(E[] arr, Merger<E> merger) {

        this.merger = merger;
        data = (E[])new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }

        /**
         * 4 * arr.length: 是因为需要使用数组, 构建一棵树;
         * 是一个平衡二叉树; 因此h层的元素需要2^n-1; 可能还有元素落于n + 1层; 因此需要 4n的位置;
         * 方才能够使用数组管理一棵树.
         */
        tree = (E[])new Object[4 * arr.length];
        buildSegmentTree(0, 0, data.length - 1);
    }

    /**
     * 在treeIndex的位置创建表示区间[l...r]的线段树
     */
    private void buildSegmentTree(int treeIndex, int l, int r) {
        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }

        int leftChildIndex = leftChild(treeIndex);
        int rightChildIndex = rightChild(treeIndex);

        int mid = l + (r - l) / 2;

        buildSegmentTree(leftChildIndex, l, mid);
        buildSegmentTree(rightChildIndex, mid + 1, r);

        // 对于treeIndex位置的数据处理, 根据传入的Merger对象决定进行什么操作.
        tree[treeIndex] = merger.merger(tree[leftChildIndex], tree[rightChildIndex]);
    }

    /**
     * 返回线段树中元素的个数.
     */
    public int getSize() {
        return data.length;
    }

    /**
     * 根据index, 获取对应位置的元素.
     */
    public E get(int index) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("Index is error!");
        }

        return data[index];
    }

    /**
     * 返回数组表示的二叉树中, 一个索引所表示的元素的左孩子节点的索引
     */
    private int leftChild(int index) {
        return  2 * index + 1;
    }

    /**
     * 返回数组表示的二叉树中, 一个索引所表示的元素的右孩子节点的索引
     */
    private int rightChild(int index) {
        return 2 * index + 2;
    }

    /**
     * 返回区间[queryL...queryR]的值
     */
    public E query(int queryL, int queryR) {
        if (queryL < 0 || queryL >= data.length || queryR < 0 ||
                queryR >= data.length || queryL > queryR) {
            throw new IllegalArgumentException("Index is illegal!");
        }

        return query(0, 0, data.length - 1, queryL, queryR);
    }

    /**
     * 以treeIndex为根的线段树中[left...right]的范围里, 搜索区间(queryL...queryR)的值
     */
    private E query(int treeIndex, int left, int right, int queryL, int queryR) {
        if (left == queryL && right == queryR) {
            return tree[treeIndex];
        }

        int mid = left + (right - left) / 2;
        int leftChildIndex = leftChild(treeIndex);
        int rightChildIndex = rightChild(treeIndex);

        if (queryR <= mid) {
            // 说明, 区间落在了treeIndex的左子树中.
            return query(leftChildIndex, left, mid, queryL, queryR);
        } else if (queryL > mid) {
            // 说明, 区间落在了treeIndex的右子树中.
            return query(rightChildIndex, mid + 1, right, queryL, queryR);
        }

        // 不在上面两种情况中, 表示区间落在了左子树和右子树中的一部分上.
        E leftResult = query(leftChildIndex, left, mid, queryL, mid);
        E rightResult = query(rightChildIndex, mid + 1, right, mid + 1, queryR);
        return merger.merger(leftResult, rightResult);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < tree.length; i++) {
            if (tree[i] != null) {
                res.append(tree[i]);
            } else {
                res.append("NULL");
            }

            if (i != data.length - 1) {
                res.append(", ");
            }
        }

        return res.toString();
    }
}
